class Solution():
    def partition(self, s):
        if (s == ''): return []
        e = []
        if (s == s[::-1]): e.append([s])
        for i in range(len(s)):
            if (s[:i + 1] == s[i::-1]):
                p = self.partition(s[i + 1:])
                for c in p:
                    if (c != []): e.append([s[:i + 1]] + c)

        return e
test = Solution()
print(test.partition('aab'))




class Solution(object):
    
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        self.res = []
        for i in range(len(s)):
            one_res = []
            if self.judgePal(s[:i+1]):
                one_res.append(s[:i+1])
                self.helper(s[i+1:], one_res[:])
        return self.res
    
    def helper(self, s, one_res):
        if not s:
            self.res.append(one_res)
        for i in range(len(s)):
            one_res_copy = one_res[:]
            if self.judgePal(s[:i+1]):
                one_res_copy.append(s[:i+1])
                self.helper(s[i+1:], one_res_copy)
    def judgePal(self, string):
        if not string:
            return False
        return string == string[::-1]